package org.shj.algorithm.string;

import java.util.Arrays;

/**
 * 完美洗牌问题：
 * 长度为 2n 的数组 [a1, a2, a3, a4, b1, b2, b3, b4]， 经过整理后，变
 * 成 [a1, b1, a2, b2, a3, b3, a4, b4]。
 * 要求时间复杂度为 O(N)，空间复杂度为 O(1)
 *
 *
 * @author Shen Huang Jian
 * @date 2019/5/3
 */
public class PerfectShuffle {

    public static void main(String[] args){
        //String[] array = {"a1", "a2", "a3", "a4", "b1", "b2", "b3", "b4"};
        String[] array = {"a1", "a2", "a3", "a4", "a5","a6", "a7", "b1", "b2", "b3", "b4", "b5", "b6", "b7"};
        //method1(array);
        method2(array);

    }

    /**
     * 步骤：
     * 1. 交换中间一对数，得到
     *    a1, a2, a3, b1, a4, b2, b3, b4
     * 2. 交换最中间的两对数：
     *    a1, a2, b1, a3, b2, a4, b3, b4
     * 3. 交换最中间的三对数
     *    a1, b1, a2, b2, a3, b3, a4, b4
     * 以上算法看起来不错，但是时间复杂度是 N 的平方的
     */
    private static void method1(String[] array){
        //略
    }

    /**
     * 要想达到 O(N) 的时间复杂度，必须知道每个数最终的位置。把上面的问题转化一下，
     * 1. 先排成 [b1, a1, b2, a2, b3, a3, b4, a4],
     * 2. 然后再两两交换
     * 因为第2步是满足要求的，所以，第1步满足要求即可。
     * 以 n=4 为例，各个位置的元素变换如下:
     * 前 n 个数:    1 -> 2  (表示 第 1 个数最后的位置是 2)
     *              2 -> 4
     *              3 -> 6
     *              4 -> 8
     * 后 n 个数：   5 -> 1
     *              6 -> 3
     *              7 -> 5
     *              8 -> 7
     * 通过观察可以得出：
     * 前 n 个数的最终的位置是 2*i， 其中 i 是其原始的下标位置（以 1 为第一个的下标）, 因为
     *    i <= n, 所以 2*i = 2*i %(2*n+1)
     * 后 n 个数的最终的位置是 2*i-2*n-1, 因为 n < i <= 2n， 所以
     *    2*i-2*n-1=2*i-(2*n+1) = 2*i % (2*n+1)
     * 由上面可以看出存在两个环：
     *    1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1
     *    3 -> 6 -> 3
     *     如何求出有几个环？由完美洗牌算法的发明者得出下面的结论，
     * 对于 2*n=3^k-1 这种长度的数组，恰好只有 k 个圈，且每个圈的起始位置
     * 分别是 1, 3, 9, ..., 3^(k-1)
     *     那么如何处理 2*n 无法用 3^k -1 表示的数组呢？步骤如下（图参见 pic/完美洗牌.png）：
     * (1) 找出一个最大的 m，使得 2*m 可以表示成 3^k -1
     * (2) 问题可以分解成图中前面的 m 段与 2m-n加上蓝色的n-m 段进行完美洗牌，并且紫色的 n-m 段
     *     与绿色的 n-m 段进行完美洗牌
     * (3) 为了利用上面的结论，可以把 2m-n加上蓝色的n-m 段与紫色的 n-m 段进行循环左移 n-m 位
     * (4) 这样前面的 2*m 段可以利用上面的结论，得出结果
     * (5) 对于后面的 2*(n-m) 段，可以重复（1）~（4）的步骤，直到 2*(n-m) 只有两个数
     *
     * @param array
     */
    private static void method2(String[] array){
        processArray(array, 1, array.length);
        Arrays.asList(array).stream().forEach(item -> {
            System.out.print(item + ", ");
        });
        System.out.println();
    }

    private static void processArray(String[] array, int from, int to){
        int n = (to - from + 1) / 2;
        if(n == 1){
            String tmp = array[from-1];
            array[from-1] = array[to-1];
            array[to-1] = tmp;
            return;
        }
        int k = (int)Math.pow(2*n+1, 1.0/3);
        if(Math.pow(3,k) - 1 == 2*n){ // 如果能表示成 2*n=3^k-1
            for(int i = 1; i <= k; i++){
                cycleMove(array, (int)Math.pow(3, (i-1)), 2*n + 1, from);
            }
        }else{
            int m = (int)(Math.pow(3,k) - 1) / 2;

            //说明中的第（3）步
            leftMove(array, m + from, m+n+from-1, n-m);

            //说明中的第（4）步
            k = (int)Math.pow(2*m+1, 1.0/3);
            for(int i = 1; i <= k; i++){
                cycleMove(array, (int)Math.pow(3, (i-1)), 2*m + 1, from-1);
            }

            //说明中的第（5）步
            processArray(array, 2*m+1 + (from-1), 2*n + (from-1));

        }
    }

    /**
     * 此方法的说明详见 LoopLeftMove.java。
     * 此方法只移动 [from,to] 的部分。此方法中的 from, to 均为 java 中的下标+1
     * @param arr
     * @param from 开始位置
     * @param to 起始位置
     * @param move 移动多少位
     */
    private static void leftMove(String[] arr, int from, int to, int move){
        int length = to - from + 1;

        int k = move % length;

        reverse(arr, from-1, k - 1 + (from-1));
        reverse(arr, k -1 + from, to-1);
        reverse(arr, from-1, to-1);
    }

    private static void reverse(String[] arr, int from, int to){
        String tmp;
        while(from < to){
            tmp = arr[from];
            arr[from++] = arr[to];
            arr[to--] = tmp;
        }
    }

    /**
     *
     * @param array
     * @param from
     * @param mod 说明中的 2*n+1
     */
    private static void cycleMove(String[] array, int from, int mod, int offset){
        String tmp;
        //注释中提到的位置下标都是从 1 开始的，java 中的下标，需要相应减 1
        int next = from;
        do{
            tmp = array[next-1 + offset];
            array[next-1 + offset] = array[from-1 + offset];
            array[from-1 + offset] = tmp;
            next = 2*next % mod;
        }while(next != from);
    }

}
